class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        // 搜索左右边界
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);

        return {left, right};
    }

    // 搜索左侧边界
    int searchLeft(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1; // 左闭右闭

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] == target)
            {
                // 收缩右侧边界
                right = mid - 1;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
        }

        // 注意判断
        if(left >= nums.size() || nums[left] != target)
        {
            return -1;
        }

        return left;
    }

    // 搜索右侧边界
    int searchRight(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] == target)
            {
                // 收缩左侧边界
                left = mid + 1;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
        }

        if(right < 0 || nums[right] != target)
        {
            return -1;
        }

        return right;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else if(nums[mid] == target)
            {
                return mid;
            }
        }

        return -1;
    }
};


class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else if(nums[mid] == target)
            {
                return mid;
            }
        }

        return -1;
    }
};


